1. Field of the Invention
The present invention relates to a database management system for locking data in a plurality of databases during the execution of a transaction.
2. Discussion of the Related Art
A plurality of computers can be arranged in a distributed database system, each computer having a database. The plurality of computers are interconnected by communication lines. Each computer manages its own database (computer and associated own database are called "node" herein). When a node is supplied with a data processing request through an input device, the computer in the node checks which database includes the necessary data for the requested processing, by referring to a table of stored data names nd corresponding locations. If the data is included in the node's own database, the computer reads the data from this database, executes the data processing program and writes the result into the database (a series of such processes is called a "transaction"). If some data is included not only in the node's own database but also in a database of a second node, the computer sends the processing request to the second node, the database of which includes the data. The computer at the second node then reads the data from its database, executes the data processing at its node and writes the data processing result to its database, according to the processing request. In such cases, during processing of the transaction by using the data in the database, other computers at other nodes must not access the same data to execute the other transaction. If the other computer accesses the same data, the resultant data in the database will be inconsistent.
For example, FIG. 1 shows an example of two computers attempting to access the same data item. For instance assume the node is the branch of a bank and its database stores the deposit balance. When the node receives money from the user, a transaction takes place. The deposit balance is read from user's account, the received money is added to the deposit balance and the result is written to his account. Assume that the database of node A stores the user X's deposit balance of $50 and a deposit of $100 is received at node A deposited by user X (this transaction is called Ta). Immediately thereafter, assume that another node B receives $30 for user X's account deposited by user Y (this transaction is called Tb). First, the computer at node A executes READ(Ta). As user X's deposit balance is $50, the computer adds the received $100 to $50 and writes $150 as being the current balance. (WRITE(Ta)). However, the computer at node B executes READ (Tb) before WRITE(Ta). The computer at node B reads user X's deposit balance of $50 through the communication line. Then, the node B computer adds the $30 received to $50 and writes $80 in user X's account as the balance (WRITE (Tb)). Therefore, user X's deposit balance will be $80. However, actually user X's deposit balance should be $180.
Therefore, in the prior art, a lock method is used to prevent occurrence of this type of problem. According to this method, before the computer at node A executes READ(Ta), the computer at node A sets a flag corresponding to user X's account in database A. This flag prohibits access by other computers. When the computer at node A finishes WRITE(Ta), the computer of node A resets the flag corresponding to user X's account in database A. Therefore, during the execution of transaction (Ta), the computer at node B delays executing transaction (Tb) because a flag corresponding to user X's account is set. After the flag is reset by the computer at node A, the computer at node B executes transaction (Tb). The lock method prevents generating incorrect data. However, in the lock method, a so-called deadlock between a plurality of transactions can occur. FIG. 2A, 2B, 2C and 2D show an example of how deadlock between two transactions can occur. It is assumed that transaction A begins to lock other transactions out from two data i and j; transaction B also begins to lock out other transactions from the two data i and j, too. The lock operation is executed as follows.
(1) transaction A locks data item i (FIG. 2A). PA1 (2) transaction B locks data item j (FIG. 2B). PA1 (3) transaction A tries to lock data item j, but must wait until data item j is released (FIG. 2C). PA1 (4) transaction B tries to lock data item i, but must wait until data item i is released (FIG. 2D). PA1 (1) transaction A locks out other transactions from data items i and j at the same time. PA1 (2) transaction B tries to lock out data items i and j, but must wait until transaction A releases data items i and j. PA1 (1) transaction B locks out other transactions from data items i and j at the same time. PA1 (2) transaction A tries to lock out data items i and j, but must wait until transaction B releases data items i and j.
When both transactions A and B must wait until a required data item is released by the other transaction, as in this example, dead lock occurs. In this case, the cause of the deadlock is that transaction B has locked data item j before transaction A was able to lock data item j. However, if only one of transactions A and B locks both data items i and j at the same time, such a deadlock between transactions will not happen. When the first transaction releases data items i and j, the other transaction can lock both data items i and j. In short, deadlock does not occur. In such a case, two possible sequences can occur.
FIG. 3A shows the first sequence as follows:
FIG. 3B shows the second sequence as follows:
In these two situations, one transaction gains exclusive access to both data items i and j. Therefore, the transaction finishes before the two data items i and j are released. Only then can the other transaction gain access to both data items i and j.
However, in a distributed database system, the locking procedure is executed through communication lines between databases. For example, it is assumed that data items i and j are included in database A and B respectively, node A includes computer A and database A, node B includes computer B and database B. Accordingly, transaction of computer A locks out other transactions from data item j in database B later than when transaction of computer A locks data item i in database A because there is a communication delay between computer A and database B. Likewise, when transaction of computer B locks data item i in database A later than when transaction of computer B locks data item j in database B because there is communication delay between computer B and database A. Therefore, in prior art data base management systems, it is difficult for a transaction to lock out the other transactions from plural data items in distributed databases at the same time.